package data.structure.bplustree;

import java.util.Random; 
/**
       B-树是一种多路搜索树（并不是二叉的）：它有如下特性

       1.定义任意非叶子结点最多只有M个儿子；且M>2；

       2.根结点的儿子数为[2, M]；

       3.除根结点以外的非叶子结点的儿子数为[M/2, M]；

       4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

       5.非叶子结点的关键字个数=指向儿子的指针个数-1；

       6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

       7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的

                       子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

       8.所有叶子结点位于同一层；  如：（M=3）
       B+树是B-树的变体，也是一种多路搜索树：其定义基本与B-树同，除了：

       1.非叶子结点的子树指针与关键字个数相同；

       2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树

（B-树是开区间）；

       3.为所有叶子结点增加一个链指针；

       4.所有关键字都在叶子结点出现；如：（M=3）
 * @author Administrator
 *
 */
public class BplusTree implements BTreeOperation { 
     
    /** 根节点 */ 
    protected Node root; 
     
    /** 阶数，M值 */ 
    protected int order; 
     
    /** 叶子节点的链表头*/ 
    protected Node head; 
     
    public Node getHead() { 
        return head; 
    } 
 
    public void setHead(Node head) { 
        this.head = head; 
    } 
 
    public Node getRoot() { 
        return root; 
    } 
 
    public void setRoot(Node root) { 
        this.root = root; 
    } 
 
    public int getOrder() { 
        return order; 
    } 
 
    public void setOrder(int order) { 
        this.order = order; 
    } 
 
    @Override 
    public Object get(Comparable key) { 
        return root.get(key); 
    } 
 
    @Override 
    public void remove(Comparable key) { 
        root.remove(key, this); 
 
    } 
 
    @Override 
    public void insertOrUpdate(Comparable key, Object obj) { 
        root.insertOrUpdate(key, obj, this); 
 
    } 
     
    public BplusTree(int order){ 
        if (order < 3) { 
            System.out.print("order must be greater than 2"); 
            System.exit(0); 
        } 
        this.order = order; 
        root = new Node(true, true); 
        head = root; 
    } 
     
    //测试 
    public static void main(String[] args) { 
        BplusTree tree = new BplusTree(6); 
        Random random = new Random(); 
        long current = System.currentTimeMillis(); 
        for (int j = 0; j < 100000; j++) { 
            for (int i = 0; i < 100; i++) { 
                int randomNumber = random.nextInt(1000); 
                tree.insertOrUpdate(randomNumber, randomNumber); 
            } 
 
            for (int i = 0; i < 100; i++) { 
                int randomNumber = random.nextInt(1000); 
                tree.remove(randomNumber); 
            } 
        } 
 
        long duration = System.currentTimeMillis() - current; 
        System.out.println("time elpsed for duration: " + duration); 
        int search = 80; 
        System.out.print(tree.get(search)); 
    } 
 
} 